'''
二分查找(折半查找):要求查找对象是有序表,有递归和非递归
时间复杂度:最优 O(1)  最坏 O(log n)
'''


def binary_search(list, item):
    '''递归二分查找'''
    n = len(list)
    if n == 0:
        return False
    mid = n // 2
    if list[mid] == item:
        return True
    elif list[mid] > item:
        return binary_search(list[:mid], item)
    else:
        return binary_search(list[mid + 1:], item)


def binary_find(list, item):
    '''非递归查找'''
    n = len(list)
    if n == 0:
        return False
    start = 0
    end = n - 1

    while start <= end:
        mid = (start + end) // 2
        if list[mid] == item:
            return True
        elif list[mid] > item:
            end = mid - 1
        else:
            start = mid + 1

    return False


if __name__ == '__main__':
    list = [23, 45, 47, 55, 69, 71, 89, 100]
    print(binary_search(list, 89))
    print(binary_search(list, 19))
    print(binary_find(list, 819))
    print(binary_find(list, 45))
